package com.xy6.struct.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

/**
 * 无向图
 * 
 * <pre>
 * 邻接矩阵表示
（1）建立一个无向图的邻接表。
（2）输出该邻接表。
（3）在无向图的邻接表的基础上计算各顶点的度，并输出。
（5）采用邻接表存储实现无向图的深度优先遍历。
（6）采用邻接表存储实现无向图的广度优先遍历。
（7）无向图求最小生成树
（8）无向图求任意两点最短路径 
 * </pre>
 * 
 * @author zhang
 * @since 2017-10-03
 */
public class UndirectedGraph {

	/** 顶点 */
	private int[] vertex;
	
	/** 边 */
	private int[][] edge;
	
	/** 度 */
	private int[] degree;

	public UndirectedGraph(){
	}
	
	public UndirectedGraph(int[] v, int[][] e){
		this.vertex = v;
		this.edge = e;
		init();
	}
	
	/**
	 * 初始化顶点的度等数据
	 */
	private void init(){
		degree();
	}
	
	public int[] getVertex() {
		return vertex;
	}

	public void setVertex(int[] vertex) {
		this.vertex = vertex;
	}
	
	public int[][] getEdge() {
		return edge;
	}

	public void setEdge(int[][] edge) {
		this.edge = edge;
	}

	/**
	 * 输出图的各边
	 */
	public void print(){
		if(null == vertex || vertex.length == 0){
			System.out.println("empty graph");
			return;
		}
		System.out.println("vertex:" + Arrays.toString(vertex));
		System.out.println("edge:");
		for (int i = 0; i < edge.length; i++) {
			for (int j = 0; j < edge[i].length; j++) {
				if(edge[i][j] <= 0){
					continue;
				}
				System.out.println(String.format("%d-%d: %d", i, j,edge[i][j]));
			}
		}
	}
	
	/**
	 * 计算各顶点的度
	 */
	private void degree(){
		if(null == vertex || vertex.length == 0){
			return;
		}
		degree = new int[vertex.length];
		for (int i = 0; i < edge.length; i++) {
			int count = 0;
			for (int j = 0; j < edge[i].length; j++) {
				if(edge[i][j] <= 0){
					continue;
				}
				count++;
			}
			degree[i] = count;
		}
	}
	
	/**
	 * 输出各顶点的度
	 */
	public void printDegree(){
		if(null == degree || degree.length == 0){
			return;
		}
		for (int i = 0; i < degree.length; i++) {
			System.out.println(String.format("%d: %d", i, degree[i]));
		}
	}
	
	/**
	 * 深度优先遍历
	 */
	public void iteratorDFS(){
		if(null == degree || degree.length == 0){
			return;
		}
		Map<String, String> map = new LinkedHashMap<>(vertex.length);
		for(int i=0; i<vertex.length; i++){
			dfs(i, map);
		}
	}

	/**
	 * 深度优先遍历
	 * 
	 * @param v
	 * @param map
	 */
	private void dfs(int v, Map<String, String> map){
		for (int i = 0; i < edge[v].length; i++) {
			if (edge[v][i] <= 0) {
				continue;
			}
			if (map.containsKey(i + "" + v) || map.containsKey(v + "" + i)) {
				continue;
			}
			map.put(v + "" + i, null);
			System.out.println(String.format("%d-%d: %d", v, i, edge[v][i]));
			dfs(i, map);
		}
	}
	
	/**
	 * 广度优先遍历
	 */
	public void iteratorBFS(){
		if(null == degree || degree.length == 0){
			return;
		}
		Map<String, String> map = new LinkedHashMap<>(vertex.length);
		for (int i = 0; i < edge.length; i++) {
			for (int j = 0; j < edge[i].length; j++) {
				if(edge[i][j] <= 0){
					continue;
				}
				if (map.containsKey(i + "" + j) || map.containsKey(j + "" + i)) {
					continue;
				}
				map.put(i + "" + j, null);
				System.out.println(String.format("%d-%d: %d", i, j, edge[i][j]));
			}
		}
	}
	
	/**
	 * 最小生成树
	 * <pre>
	 * Prim算法
	 * 图的存贮结构采用邻接矩阵.
	 * 此方法是按各个顶点连通的步骤进行,需要用一个顶点集合,
	 * 开始为空集,以后将以连通的顶点陆续加入到集合中,
	 * 全部顶点加入集合后就得到所需的最小生成树 
	 * </pre>
	 */
	public void getMinTreePrim(){
		int num = vertex.length;
		List<String> allV = new ArrayList<>(num);
		for(int i=0; i<num; i++){
			allV.add(String.valueOf(vertex[i]));
		}
		List<String> newV = new ArrayList<>(num);
		int[][] newE = new int[num][num];

		addVertex(0, newV, allV, newE);

		System.out.println("min tree:");
		for (int i = 0; i < newE.length; i++) {
			for (int j = 0; j < newE[i].length; j++) {
				if(newE[i][j] <= 0){
					continue;
				}
				System.out.println(String.format("%d-%d: %d", i, j,newE[i][j]));
			}
		}
	}
	
	/**
	 * 递归添加一个点到最小生成树中
	 * 
	 * @param v
	 * @param newV
	 * @param allV
	 * @param newE
	 */
	private void addVertex(int v, List<String> newV, List<String> allV, int[][] newE) {
		newV.add(String.valueOf(v));
		allV.remove(String.valueOf(v));
		int min = -1;
		int start = -1;
		int end = -1;
		System.out.println("newV:" + newV);
		System.out.println("allV:" + allV);
		
		// 查找newV -> allV最短的一条边
		for (String str1 : newV) {
			int i = Integer.valueOf(str1);
			for (String str2 : allV) {
				int j = Integer.valueOf(str2);
				if(edge[i][j] <= 0){
					continue;
				}
				// min取第1个不为0的边
				if(min == -1){
					min = edge[i][j];
					start = i;
					end = j;
				}
				if(edge[i][j] < min){
					min = edge[i][j];
					start = i;
					end = j;
				}
			}
		}
		// 未找到
		if(min == -1){
			return;
		}
		System.out.println(String.format("%d-%d: %d", start, end, min));
		// 更新最小生成树
		newE[start][end] = min;
		newE[end][start] = min;
		
		addVertex(end, newV, allV, newE);
	}
	
	/**
	 * 查找两点之间的最短路径，Floyd算法
	 * <pre>
	 * 时间复杂度：O(n^3)
	 * </pre>
	 */
	public void getMinPathFloyd(){
		// TODO
	}
	
	/**
	 * 查找两点之间的最短路径
	 * <p>深度优先搜索
	 * 
	 * @param i
	 * @param j
	 */
	public void getMinPathDFS(int i, int j){
		if(i == j){
			System.out.println(String.format("%d=%d", i, j));
			return;
		}
		if(i > j){
			int temp = i;
			i = j;
			j = temp;
		}
		Map<String, Integer> map = new LinkedHashMap<>();
		List<String> visited = new ArrayList<>(vertex.length);
		searchDFS(i, j, i, map, visited);
		
		// 过滤出目标路径
		Iterator<Entry<String, Integer>> iter = map.entrySet().iterator();
		while(iter.hasNext()){
			Entry<String, Integer> entry = iter.next();
			String key = entry.getKey();
			if(!key.startsWith(String.valueOf(i)) || !key.endsWith(String.valueOf(j))){
				iter.remove();
			}
		}
		System.out.println(map);
		if(map.isEmpty()){
			System.out.println("no available path");
			return;
		}
		
		// 按路径长度升序排列。稳定？
		List<Map.Entry<String, Integer>> elems = new ArrayList<>(map.size());
		for(Map.Entry<String, Integer> elem : map.entrySet()){
			elems.add(elem);
		}
		Collections.sort(elems, new Comparator<Map.Entry<String, Integer>>(){
			@Override
			public int compare(Entry<String, Integer> elem1, Entry<String, Integer> elem2) {
				return elem1.getValue() - elem2.getValue();
			}
		});
		System.out.println("paths:" + elems);
		// 将路径转换为邻接矩阵
		int newE[][] = new int[vertex.length][vertex.length];
		String strPath = elems.get(0).getKey();
		List<Integer> vertexs = new ArrayList<>(strPath.length());
		for(int k = 0; k<strPath.length(); k++){
			vertexs.add(Integer.valueOf(String.valueOf(strPath.charAt(k))));
		}
		for (int k = 0; k < vertexs.size() - 1; k++) {
			int start = vertexs.get(k);
			int end = vertexs.get(k + 1);
			newE[start][end] = edge[start][end];
			newE[end][start] = edge[end][start];
		}
		
		System.out.println("min tree:");
		for (int m = 0; m < newE.length; m++) {
			for (int n = 0; n < newE[i].length; n++) {
				if(newE[m][n] <= 0){
					continue;
				}
				System.out.println(String.format("%d-%d: %d", m, n,newE[m][n]));
			}
		}
	}

	/**
	 * 查找两点之间的所有路径
	 * 
	 * @param start 始点。固定
	 * @param end 终点。固定
	 * @param v 当前遍历的起点
	 * @param map 路径集合
	 * @param visited 当前遍历访问过的点
	 */
	private void searchDFS(int start, int end, int v, Map<String, Integer> map, List<String> visited){
		System.out.println("---");
		visited.add(String.valueOf(v));
		System.out.println("visited1:" + visited);
		for (int i = 0; i < edge[v].length; i++) {
			if (edge[v][i] <= 0) {
				continue;
			}
			if(visited.contains(String.valueOf(i))){
				continue;
			}
			System.out.println(String.format("v:%d, i:%d", v, i));
			// 添加路径，或延长路径
			if(map.isEmpty()){
				map.put(v + "" + i, edge[v][i]);
			} else {
				if(v == start){
					map.put(v + "" + i, edge[v][i]);
				} else{
					Map<String, Integer> temp = new HashMap<>(vertex.length);
					// 查找待延长的路径
					for(String elem : map.keySet()){
						// 路径终点为线段起点，路径中没有线段终点，路径中没有延长后的路径
						if(elem.endsWith(String.valueOf(v)) && elem.indexOf(String.valueOf(i)) < 0 && !map.containsKey(elem + i)){
							temp.put(elem + i, map.get(elem) + edge[v][i]);
						}
					}
					if(!temp.isEmpty()){
						map.putAll(temp);
						temp = null;
					}
					// 不确定temp元素何时>1，加断言
					assert temp.size() <= 1 : "";
				}
			}
			
			System.out.println("map:" + map);
			// 终止当前查找
			if(i == end){
				continue;
			}
			searchDFS(start, end, i, map, visited);
			System.out.println("visited remove:" + i);
			visited.remove(String.valueOf(i));
		}
		System.out.println("visited2:" + visited);
	}
	
	/**
	 * 迪杰斯特拉算法，查找两点之间最短路径
	 * 
	 * @param start
	 * @param end
	 */
	public void getMinPathDijkstra(int start, int end){
		Map<String, Integer> map = new LinkedHashMap<>();
		List<String> visit = new ArrayList<>(vertex.length);
		List<String> unvisit = new ArrayList<>(vertex.length);
		for(int elem : vertex){
			unvisit.add(elem + "");
		}
		
		searchDijkstra(start, end, start, map, unvisit, visit);
		
		System.out.println(map);
		System.out.println("visit:" + visit);
		System.out.println("unvisit:" + unvisit);
		// 计算起点到终点的距离
		Map<String, Map.Entry<String, Integer>> pairs = new LinkedHashMap<>(map.size());
		for(Map.Entry<String, Integer> elem : map.entrySet()){
			pairs.put(elem.getKey().charAt(1) + "", elem);
		}
		if(!pairs.containsKey(end + "")){
			System.out.println("no available path");
			return;
		}
		int len = 0;
		String v = end + "";
		List<String> path = new ArrayList<>(map.size());
		while (true) {
			path.add(v);
			if(!pairs.containsKey(v)){
				break;
			}
			len += pairs.get(v).getValue();
			v = pairs.get(v).getKey().charAt(0) + "";
		}
		// 路径倒序
		List<String> newPath = new ArrayList<>(map.size());
		for (int i = path.size() - 1; i >= 0; i--) {
			newPath.add(path.get(i));
		}
		System.out.println("path:" + newPath);
		System.out.println("minD:" + len);
	}

	/**
	 * 迪杰斯特拉算法，查找两点之间最短路径
	 * <pre>
	 * http://blog.csdn.net/mu399/article/details/50903876
	 * 假设4个点：0、1、2、3
	 * 1 集合A={}, B={0,1,2,3}
	 * 2 集合A={0}, B={1,2,3}，计算A到B的最短路径，得到0-1=d1，将1加入A
	 * 3 集合A={0,1}, B={2,3}，计算A到B的最短路径，得到1-2=d2，将2加入A
	 * 3 集合A={0,1,2}, B={3}，计算A到B的最短路径，得到0-3=d3，将3加入A
	 * 4 集合A={0,1,2,3}，B={}，计算终止，得到map={0-1=d1,1-2=d2,0-3=d3}
	 * 5 根据map计算0到2之间的距离：根据2找到1-2=d2，根据1找到0-1=d1。
	 * 因此总长度为min(0-2)=d1+d2，路径为2-1-0逆序，0-1-2
	 * </pre>
	 * 
	 * @param start
	 * @param end
	 * @param v
	 * @param map
	 * @param visited
	 */
	private void searchDijkstra(int start, int end, int v, Map<String, Integer> map, List<String> unvisit, List<String> visit){
		System.out.println("---");
		System.out.println("map:" + map);
		visit.add(v + "");
		unvisit.remove(v + "");
		if(v == end){
			return;
		}
		// 计算点集A到点集B的最短路径
		int minD = Integer.MAX_VALUE;
		int from = -1;
		int to = -1;
		for (int i = 0; i < visit.size(); i++) {
			for (int j = 0; j < unvisit.size(); j++) {
				int v1 = Integer.valueOf(visit.get(i));
				int v2 = Integer.valueOf(unvisit.get(j));
				if(edge[v1][v2] <= 0){
					continue;
				}
				if(edge[v1][v2] < minD){
					minD = edge[v1][v2];
					from = v1;
					to = v2;
				}
			}
		}
		System.out.println(String.format("A:%s, B:%s, min:%d-%d=%d", visit.toString(), unvisit.toString(), from, to,
				minD));
		
		// 未找到最短路径
		if(from == -1){
			return;
		}
		map.put(from + "" + to, minD);
		searchDijkstra(start, end, to, map, unvisit, visit);
	}
	
}
